{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Trailing Zeros in a Cornered Path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxTrailingZeros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #转角路径的乘积中最多能有几个尾随零"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二维整数数组 <code>grid</code> ，大小为 <code>m x n</code>，其中每个单元格都含一个正整数。</p>\n",
    "\n",
    "<p><strong>转角路径</strong> 定义为：包含至多一个弯的一组相邻单元。具体而言，路径应该完全 <strong>向水平方向</strong> 或者 <strong>向竖直方向</strong> 移动过弯（如果存在弯），而不能访问之前访问过的单元格。在过弯之后，路径应当完全朝 <strong>另一个</strong> 方向行进：如果之前是向水平方向，那么就应该变为向竖直方向；反之亦然。当然，同样不能访问之前已经访问过的单元格。</p>\n",
    "\n",
    "<p>一条路径的 <strong>乘积</strong> 定义为：路径上所有值的乘积。</p>\n",
    "\n",
    "<p>请你从 <code>grid</code> 中找出一条乘积中尾随零数目最多的转角路径，并返回该路径中尾随零的数目。</p>\n",
    "\n",
    "<p>注意：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>水平</strong> 移动是指向左或右移动。</li>\n",
    "\t<li><strong>竖直 </strong>移动是指向上或下移动。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/23/ex1new2.jpg\" style=\"width: 577px; height: 190px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>左侧的图展示了一条有效的转角路径。\n",
    "其乘积为 15 * 20 * 6 * 1 * 10 = 18000 ，共计 3 个尾随零。\n",
    "可以证明在这条转角路径的乘积中尾随零数目最多。\n",
    "\n",
    "中间的图不是一条有效的转角路径，因为它有不止一个弯。\n",
    "右侧的图也不是一条有效的转角路径，因为它需要重复访问已经访问过的单元格。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/03/25/ex2.jpg\" style=\"width: 150px; height: 157px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[4,3,2],[7,6,1],[8,8,8]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>网格如上图所示。\n",
    "不存在乘积含尾随零的转角路径。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-trailing-zeros-in-a-cornered-path](https://leetcode.cn/problems/maximum-trailing-zeros-in-a-cornered-path/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-trailing-zeros-in-a-cornered-path](https://leetcode.cn/problems/maximum-trailing-zeros-in-a-cornered-path/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[23,17,15,3,20],[8,1,20,27,11],[9,4,6,2,21],[40,9,1,10,6],[22,7,4,5,3]]', '[[4,3,2],[7,6,1],[8,8,8]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "def I():\n",
    "    return input()\n",
    "\n",
    "def II():\n",
    "    return int(input())\n",
    " \n",
    "def MII():\n",
    "    return map(int, input().split())\n",
    " \n",
    "def LI():\n",
    "    return list(input().split())\n",
    " \n",
    "def LII():\n",
    "    return list(map(int, input().split()))\n",
    " \n",
    "def GMI():\n",
    "    return map(lambda x: int(x) - 1, input().split())\n",
    " \n",
    "def LGMI():\n",
    "    return list(map(lambda x: int(x) - 1, input().split()))\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        dp = [[[0,0] for _ in range(n)] for _ in range(m)]\n",
    "        @cache\n",
    "        def f(x :int):\n",
    "            if x == 0:\n",
    "                return (0,0)\n",
    "            a2,a5 = 0,0\n",
    "            while x % 2 == 0:\n",
    "                a2 += 1\n",
    "                x //= 2\n",
    "            while x % 5 == 0:\n",
    "                a5 += 1\n",
    "                x //= 5\n",
    "            return (a2,a5)\n",
    "        for i in range(m):\n",
    "            dp[i][0][0],dp[i][0][1] = f(grid[i][0])\n",
    "            for j in range(1, n):\n",
    "                dp[i][j][0],dp[i][j][1] = f(grid[i][j])\n",
    "                dp[i][j][0] += dp[i][j-1][0]\n",
    "                dp[i][j][1] += dp[i][j-1][1]\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            a2,a5 = 0,0\n",
    "            for i in range(m):\n",
    "                if j == 0 or j == n-1:\n",
    "                    t2,t5 = dp[i][-1][0] + a2, dp[i][-1][1] + a5\n",
    "                    ans = max(ans, min(t2, t5))\n",
    "                else:\n",
    "                    t2,t5 = dp[i][j][0] + a2, dp[i][j][1] + a5\n",
    "                    ans = max(ans, min(t2, t5))\n",
    "                    t2,t5 = dp[i][-1][0] - dp[i][j-1][0] + a2, dp[i][-1][1] - dp[i][j-1][1]  + a5\n",
    "                    ans = max(ans, min(t2, t5))\n",
    "                t2,t5 = f(grid[i][j])\n",
    "                a2 += t2\n",
    "                a5 += t5\n",
    "        for j in range(n):\n",
    "            a2,a5 = 0,0\n",
    "            for i in range(m-1,-1,-1):\n",
    "                if j == 0 or j == n-1:\n",
    "                    t2,t5 = dp[i][-1][0] + a2, dp[i][-1][1] + a5\n",
    "                    ans = max(ans, min(t2, t5))\n",
    "                else:\n",
    "                    t2,t5 = dp[i][j][0] + a2, dp[i][j][1] + a5\n",
    "                    ans = max(ans, min(t2, t5))\n",
    "                    t2,t5 = dp[i][-1][0] - dp[i][j-1][0] + a2, dp[i][-1][1] - dp[i][j-1][1]  + a5\n",
    "                    ans = max(ans, min(t2, t5))\n",
    "                t2,t5 = f(grid[i][j])\n",
    "                a2 += t2\n",
    "                a5 += t5\n",
    "        return ans\n",
    "\n",
    "\n",
    "s = Solution()\n",
    "s.maxTrailingZeros([[437,230,648,905,744,416],[39,193,421,344,755,154],[480,200,820,226,681,663],[658,65,689,621,398,608],[680,741,889,297,530,547],[809,760,975,874,524,717]])\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2, c5 = [0] * 1001, [0] * 1001\n",
    "for i in range(2, 1001):  # 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数\n",
    "    if i % 2 == 0: c2[i] = c2[i // 2] + 1\n",
    "    if i % 5 == 0: c5[i] = c5[i // 5] + 1\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        s = [[None] * (n + 1) for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, v in enumerate(row):  # 计算 grid 每行因子 2 和 5 的前缀和\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[v], s[i][j][1] + c5[v])\n",
    "\n",
    "        ans = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            s2 = s5 = 0\n",
    "            for i, v in enumerate(col):  # 从上往下，枚举左拐还是右拐\n",
    "                s2 += c2[v]\n",
    "                s5 += c5[v]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),\n",
    "                               min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "            s2 = s5 = 0\n",
    "            for i in range(m - 1, -1, -1):  # 从下往上，枚举左拐还是右拐\n",
    "                s2 += c2[col[i]]\n",
    "                s5 += c5[col[i]]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),\n",
    "                               min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2, c5 = [0] * 1001, [0] * 1001\n",
    "for i in range(2, 1001):  # 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数\n",
    "    if i % 2 == 0: c2[i] = c2[i // 2] + 1\n",
    "    if i % 5 == 0: c5[i] = c5[i // 5] + 1\n",
    "\n",
    "class Solution:\n",
    "    # 尾零的个数就是路径上数的因子2的个数和与因子5的个数之和的较小值\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        s = [[None] * (n + 1) for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, v in enumerate(row):  # 计算 grid 每行因子 2 和 5 的前缀和\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[v], s[i][j][1] + c5[v])\n",
    "\n",
    "        ans = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            # 水平：从左往右， 竖直：从上往下\n",
    "            s2 = s5 = 0\n",
    "            for i, v in enumerate(col):  # 从上往下，枚举左拐还是右拐\n",
    "                s2 += c2[v]\n",
    "                s5 += c5[v]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),\n",
    "                               min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "            s2 = s5 = 0\n",
    "            for i in range(m - 1, -1, -1):  # 从下往上，枚举左拐还是右拐\n",
    "                s2 += c2[col[i]]\n",
    "                s5 += c5[col[i]]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),\n",
    "                               min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2, c5 = [0] * 1001, [0] * 1001\n",
    "for i in range(2, 1001):  # 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数\n",
    "    if i % 2 == 0: c2[i] = c2[i // 2] + 1\n",
    "    if i % 5 == 0: c5[i] = c5[i // 5] + 1\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        s = [[None] * (n + 1) for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, v in enumerate(row):  # 计算 grid 每行因子 2 和 5 的前缀和\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[v], s[i][j][1] + c5[v])\n",
    "\n",
    "        ans = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            s2 = s5 = 0\n",
    "            for i, x in enumerate(col):\n",
    "                s2 += c2[x]\n",
    "                s5 += c5[x]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]), min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "            s2 = s5 = 0\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                s2 += c2[col[i]]\n",
    "                s5 += c5[col[i]]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]), min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "尾零的个数就是路径上的数的因子 2 的个数和，与因子 5 的个数之和的较小值。\n",
    "那么数越多越好，路径的起点和终点都应该在边界上。\n",
    "预处理每一行的因子的前缀和，然后枚举所有的路径：\n",
    "\n",
    "从上往下走，枚举左拐/右拐；\n",
    "从下往上走，枚举左拐/右拐。\n",
    "所有路径上的 min(s2, s5) 的最大值即为答案，这里 s2 为路径上的因子 2 的个数之和，\n",
    "s5 为路径上的因子 5 的个数之和。\n",
    "'''\n",
    "c2, c5 = [0] * 1001, [0] * 1001\n",
    "for i in range(2, 1001):  # 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数\n",
    "    if i % 2 == 0: c2[i] = c2[i // 2] + 1\n",
    "    if i % 5 == 0: c5[i] = c5[i // 5] + 1\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        s = [[None] * (n + 1) for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, v in enumerate(row):  # 计算 grid 每行因子 2 和 5 的前缀和\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[v], s[i][j][1] + c5[v])\n",
    "\n",
    "        ans = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            s2 = s5 = 0\n",
    "            for i, v in enumerate(col):  # 从上往下，枚举左拐还是右拐\n",
    "                s2 += c2[v]\n",
    "                s5 += c5[v]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),\n",
    "                               min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "            s2 = s5 = 0\n",
    "            for i in range(m - 1, -1, -1):  # 从下往上，枚举左拐还是右拐\n",
    "                s2 += c2[col[i]]\n",
    "                s5 += c5[col[i]]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),\n",
    "                               min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2,c5 = [0]*1001,[0]*1001\n",
    "for i in range(2,1001):\n",
    "    if i % 2 == 0:\n",
    "        c2[i] = c2[i // 2] + 1\n",
    "    if i % 5 == 0:\n",
    "        c5[i] = c5[i // 5] + 1\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        s = [[(0,0)]*(n + 1) for _ in range(m)]\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,x in enumerate(row):\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[x],s[i][j][1] + c5[x])\n",
    "        ans = 0\n",
    "        for j,col in enumerate(zip(*grid)):\n",
    "            # 从上到下\n",
    "            s2 = s5 = 0\n",
    "            for i,x in enumerate(col):\n",
    "                s2 += c2[x]\n",
    "                s5 += c5[x]\n",
    "                ans = max(ans,min(s2 + s[i][j][0],s5 + s[i][j][1])\n",
    "                ,min(s2 + s[i][n][0] - s[i][j + 1][0],s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "            s2 = s5 = 0\n",
    "            for i in range(m - 1,-1,-1):\n",
    "                s2 += c2[col[i]]\n",
    "                s5 += c5[col[i]]\n",
    "                ans = max(ans,min(s2 + s[i][j][0],s[i][j][1] + s5)\n",
    "                ,min(s2 + s[i][n][0] - s[i][j + 1][0],s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2 = [0]*1001\n",
    "c5 = [0]*1001\n",
    "for i in range(1,1001):\n",
    "    if i % 2 == 0:\n",
    "        c2[i] = c2[i // 2] + 1\n",
    "    if i % 5 == 0:\n",
    "        c5[i] = c5[i // 5] + 1\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        s = [[(0,0)]*(n + 1) for _ in range(m)]\n",
    "        \n",
    "        for i,row in enumerate(grid):\n",
    "            for j,x in enumerate(row):\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[x],s[i][j][1] + c5[x])\n",
    "        ans = 0\n",
    "        for j,col in enumerate(zip(*grid)):\n",
    "            s2 = s5 = 0\n",
    "            for i,x in enumerate(col):\n",
    "                s2 += c2[x]\n",
    "                s5 += c5[x]\n",
    "                ans = max(ans,min(s2 + s[i][j][0],s5 + s[i][j][1]), min(s2 + s[i][-1][0] - s[i][j + 1][0],s5 + s[i][-1][1] - s[i][j + 1][1]))\n",
    "            s2 = s5 = 0\n",
    "            for i in range(m - 1,-1,-1):\n",
    "                s2 += c2[col[i]]\n",
    "                s5 += c5[col[i]]\n",
    "                ans = max(ans,min(s2 + s[i][j][0],s5 + s[i][j][1]), min(s2 + s[i][-1][0] - s[i][j + 1][0],s5 + s[i][-1][1] - s[i][j + 1][1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        def count25(v):\n",
    "            tmp2 = tmp5 = v\n",
    "            for c2 in range(1001):\n",
    "                if tmp2 % 2:\n",
    "                    break\n",
    "                tmp2 //= 2\n",
    "            for c5 in range(1001):\n",
    "                if tmp5 % 5:\n",
    "                    break\n",
    "                tmp5 //= 5\n",
    "            return c2, c5\n",
    "        c2, c5 = [0] * 1001, [0] * 1001\n",
    "        for val in range(2, 1001):\n",
    "\n",
    "            c2[val], c5[val] = count25(val) \n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        s = [[None] * (c + 1) for _ in range(r)]\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, val in enumerate(row):\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[val], s[i][j][1] + c5[val])\n",
    "        res = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            tmp_s_2 = 0\n",
    "            tmp_s_5 = 0\n",
    "            for i, val in enumerate(col):\n",
    "                tmp_s_2 += c2[val]\n",
    "                tmp_s_5 += c5[val]\n",
    "                res = max(res, min(tmp_s_2 + s[i][j][0], tmp_s_5 + s[i][j][1]),\n",
    "                min(tmp_s_2 + s[i][c][0] - s[i][j+1][0], tmp_s_5 + s[i][c][1] - s[i][j+1][1]))\n",
    "            tmp_s_2 = 0\n",
    "            tmp_s_5 = 0\n",
    "            col = col[::-1]\n",
    "            for i, val in enumerate(col):\n",
    "                i = r - 1 - i\n",
    "                tmp_s_2 += c2[val]\n",
    "                tmp_s_5 += c5[val]\n",
    "                res = max(res, min(tmp_s_2 + s[i][j][0], tmp_s_5 + s[i][j][1]),\n",
    "                min(tmp_s_2 + s[i][c][0] - s[i][j+1][0], tmp_s_5 + s[i][c][1] - s[i][j+1][1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        def count25(v):\n",
    "            tmp2 = tmp5 = v\n",
    "            for c2 in range(1001):\n",
    "                if tmp2 % 2:\n",
    "                    break\n",
    "                tmp2 //= 2\n",
    "            for c5 in range(1001):\n",
    "                if tmp5 % 5:\n",
    "                    break\n",
    "                tmp5 //= 5\n",
    "            return c2, c5\n",
    "        c2, c5 = [0] * 1001, [0] * 1001\n",
    "        for val in range(2, 1001):\n",
    "\n",
    "            c2[val], c5[val] = count25(val) \n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        s = [[None] * (c + 1) for _ in range(r)]\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, val in enumerate(row):\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[val], s[i][j][1] + c5[val])\n",
    "        res = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            tmp_s_2 = 0\n",
    "            tmp_s_5 = 0\n",
    "            for i, val in enumerate(col):\n",
    "                tmp_s_2 += c2[val]\n",
    "                tmp_s_5 += c5[val]\n",
    "                res = max(res, min(tmp_s_2 + s[i][j][0], tmp_s_5 + s[i][j][1]),\n",
    "                min(tmp_s_2 + s[i][c][0] - s[i][j+1][0], tmp_s_5 + s[i][c][1] - s[i][j+1][1]))\n",
    "            tmp_s_2 = 0\n",
    "            tmp_s_5 = 0\n",
    "            col = col[::-1]\n",
    "            for i, val in enumerate(col):\n",
    "                i = r - 1 - i\n",
    "                tmp_s_2 += c2[val]\n",
    "                tmp_s_5 += c5[val]\n",
    "                res = max(res, min(tmp_s_2 + s[i][j][0], tmp_s_5 + s[i][j][1]),\n",
    "                min(tmp_s_2 + s[i][c][0] - s[i][j+1][0], tmp_s_5 + s[i][c][1] - s[i][j+1][1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        def count25(v):\n",
    "            tmp2 = tmp5 = v\n",
    "            for c2 in range(1001):\n",
    "                if tmp2 % 2:\n",
    "                    break\n",
    "                tmp2 //= 2\n",
    "            for c5 in range(1001):\n",
    "                if tmp5 % 5:\n",
    "                    break\n",
    "                tmp5 //= 5\n",
    "            return c2, c5\n",
    "\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        s = [[None] * (c + 1) for _ in range(r)]\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, val in enumerate(row):\n",
    "                c2, c5 = count25(val)\n",
    "                s[i][j + 1] = (s[i][j][0] + c2, s[i][j][1] + c5)\n",
    "        res = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            tmp_s_2 = 0\n",
    "            tmp_s_5 = 0\n",
    "            for i, val in enumerate(col):\n",
    "                c2, c5 = count25(val)\n",
    "                tmp_s_2 += c2\n",
    "                tmp_s_5 += c5\n",
    "                res = max(res, min(tmp_s_2 + s[i][j][0], tmp_s_5 + s[i][j][1]),\n",
    "                min(tmp_s_2 + s[i][c][0] - s[i][j+1][0], tmp_s_5 + s[i][c][1] - s[i][j+1][1]))\n",
    "            tmp_s_2 = 0\n",
    "            tmp_s_5 = 0\n",
    "            col = col[::-1]\n",
    "            for i, val in enumerate(col):\n",
    "                i = r - 1 - i\n",
    "                c2, c5 = count25(val)\n",
    "                tmp_s_2 += c2\n",
    "                tmp_s_5 += c5\n",
    "                res = max(res, min(tmp_s_2 + s[i][j][0], tmp_s_5 + s[i][j][1]),\n",
    "                min(tmp_s_2 + s[i][c][0] - s[i][j+1][0], tmp_s_5 + s[i][c][1] - s[i][j+1][1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        def count25(v):\n",
    "            tmp2 = tmp5 = v\n",
    "            for c2 in range(1001):\n",
    "                if tmp2 % 2:\n",
    "                    break\n",
    "                tmp2 //= 2\n",
    "            for c5 in range(1001):\n",
    "                if tmp5 % 5:\n",
    "                    break\n",
    "                tmp5 //= 5\n",
    "            return c2, c5\n",
    "\n",
    "        r = len(grid)\n",
    "        c = len(grid[0])\n",
    "        s = [[None] * (c + 1) for _ in range(r)]\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, val in enumerate(row):\n",
    "                c2, c5 = count25(val)\n",
    "                s[i][j + 1] = (s[i][j][0] + c2, s[i][j][1] + c5)\n",
    "        res = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            tmp_s_2 = 0\n",
    "            tmp_s_5 = 0\n",
    "            for i, val in enumerate(col):\n",
    "                c2, c5 = count25(val)\n",
    "                tmp_s_2 += c2\n",
    "                tmp_s_5 += c5\n",
    "                res = max(res, min(tmp_s_2 + s[i][j][0], tmp_s_5 + s[i][j][1]),\n",
    "                min(tmp_s_2 + s[i][c][0] - s[i][j+1][0], tmp_s_5 + s[i][c][1] - s[i][j+1][1]))\n",
    "            tmp_s_2 = 0\n",
    "            tmp_s_5 = 0\n",
    "            col = col[::-1]\n",
    "            for i, val in enumerate(col):\n",
    "                i = r - 1 - i\n",
    "                c2, c5 = count25(val)\n",
    "                tmp_s_2 += c2\n",
    "                tmp_s_5 += c5\n",
    "                res = max(res, min(tmp_s_2 + s[i][j][0], tmp_s_5 + s[i][j][1]),\n",
    "                min(tmp_s_2 + s[i][c][0] - s[i][j+1][0], tmp_s_5 + s[i][c][1] - s[i][j+1][1]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "c2, c5 = [0] * 1001, [0] * 1001\n",
    "for i in range(2, 1001):  # 预处理：递推算出每个数的因子 2 的个数和因子 5 的个数\n",
    "    if i % 2 == 0: c2[i] = c2[i // 2] + 1\n",
    "    if i % 5 == 0: c5[i] = c5[i // 5] + 1\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        s = [[None] * (n + 1) for _ in range(m)]\n",
    "        for i, row in enumerate(grid):\n",
    "            s[i][0] = (0, 0)\n",
    "            for j, v in enumerate(row):  # 计算 grid 每行因子 2 和 5 的前缀和\n",
    "                s[i][j + 1] = (s[i][j][0] + c2[v], s[i][j][1] + c5[v])\n",
    "\n",
    "        ans = 0\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            s2 = s5 = 0\n",
    "            print(col)\n",
    "            for i, v in enumerate(col):  # 从上往下，枚举左拐还是右拐\n",
    "                s2 += c2[v]\n",
    "                s5 += c5[v]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),\n",
    "                               min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "            s2 = s5 = 0\n",
    "            for i in range(m - 1, -1, -1):  # 从下往上，枚举左拐还是右拐\n",
    "                s2 += c2[col[i]]\n",
    "                s5 += c5[col[i]]\n",
    "                ans = max(ans, min(s2 + s[i][j][0], s5 + s[i][j][1]),\n",
    "                               min(s2 + s[i][n][0] - s[i][j + 1][0], s5 + s[i][n][1] - s[i][j + 1][1]))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        # 分析：\n",
    "        # 路径两端肯定延长到矩阵边界是最优解\n",
    "        # 枚举转角位置，至多一个弯，可以没有弯,所以角落的元素也可以枚举\n",
    "        # 尾随0的个数 = min(cnt2,cnt5)\n",
    "\n",
    "        def f(x):\n",
    "            # 计算x中包含的0,2,5的个数\n",
    "            cnt2 = cnt5 = 0\n",
    "            t = x\n",
    "            while t:\n",
    "                if t % 2 == 0:\n",
    "                    t //= 2\n",
    "                    cnt2 += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            t = x\n",
    "            while t:\n",
    "                if t % 5 == 0:\n",
    "                    t //= 5\n",
    "                    cnt5 += 1\n",
    "                else:\n",
    "                    break\n",
    "            return cnt2,cnt5\n",
    "\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        v_cnt5 = [[0]*(m + 1) for _ in range(n)]\n",
    "        v_cnt2 = [[0]*(m + 1) for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            for i in range(1,m + 1):\n",
    "                b,c = f(grid[i - 1][j])\n",
    "                v_cnt2[j][i] = v_cnt2[j][i - 1] + b\n",
    "                v_cnt5[j][i] = v_cnt5[j][i - 1] + c\n",
    "\n",
    "        h_cnt5 = [[0]*(n + 1) for _ in range(m)]\n",
    "        h_cnt2 = [[0]*(n + 1) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(1,n + 1):\n",
    "                b,c = f(grid[i][j - 1])\n",
    "                h_cnt2[i][j] = h_cnt2[i][j - 1] + b\n",
    "                h_cnt5[i][j] = h_cnt5[i][j - 1] + c\n",
    "\n",
    "        ans = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 左+上\n",
    "                cnt2 = h_cnt2[i][j + 1] + v_cnt2[j][i]\n",
    "                cnt5 = h_cnt5[i][j + 1] + v_cnt5[j][i]\n",
    "                ans = max(ans,min(cnt2,cnt5))\n",
    "\n",
    "                # 右+上\n",
    "                cnt2 = h_cnt2[i][-1] - h_cnt2[i][j] + v_cnt2[j][i]\n",
    "                cnt5 = h_cnt5[i][-1] - h_cnt5[i][j] + v_cnt5[j][i]\n",
    "                ans = max(ans,min(cnt2,cnt5))\n",
    "\n",
    "                # 左 + 下\n",
    "                cnt2 = h_cnt2[i][j + 1] + v_cnt2[j][-1] - v_cnt2[j][i + 1]\n",
    "                cnt5 = h_cnt5[i][j + 1] + v_cnt5[j][-1] - v_cnt5[j][i + 1]\n",
    "                ans = max(ans,min(cnt2,cnt5))\n",
    "\n",
    "                # 右 + 下\n",
    "                cnt2 = h_cnt2[i][-1] - h_cnt2[i][j] + v_cnt2[j][-1] - v_cnt2[j][i + 1]\n",
    "                cnt5 = h_cnt5[i][-1] - h_cnt5[i][j] + v_cnt5[j][-1] - v_cnt5[j][i + 1]\n",
    "                ans = max(ans,min(cnt2,cnt5))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        r2,c2 = [],[]\n",
    "        r5,c5 = [],[]\n",
    "        for i in range(n):\n",
    "            cv2 = [0 for _ in range(m)]\n",
    "            cv5 = [0 for _ in range(m)]\n",
    "            for j in range(m):\n",
    "                tmp = 0\n",
    "                c = grid[i][j]\n",
    "                while c % 2 == 0:\n",
    "                    tmp += 1\n",
    "                    c //= 2\n",
    "                tmp2 = 0\n",
    "                while c % 5 == 0:\n",
    "                    tmp2 += 1\n",
    "                    c //= 5\n",
    "                if j - 1 >= 0:\n",
    "                    cv2[j] += cv2[j - 1]\n",
    "                    cv5[j] += cv5[j - 1]\n",
    "                cv2[j] += tmp\n",
    "                cv5[j] += tmp2\n",
    "            r2.append(cv2)\n",
    "            r5.append(cv5)\n",
    "        for j in range(m):\n",
    "            cv2 = [0 for _ in range(n)]\n",
    "            cv5 = [0 for _ in range(n)]\n",
    "            for i in range(n):\n",
    "                tmp = 0\n",
    "                c = grid[i][j]\n",
    "                while c % 2 == 0:\n",
    "                    tmp += 1\n",
    "                    c //= 2\n",
    "                tmp2 = 0\n",
    "                while c % 5 == 0:\n",
    "                    tmp2 += 1\n",
    "                    c //= 5\n",
    "                if i - 1 >= 0:\n",
    "                    cv2[i] += cv2[i - 1]\n",
    "                    cv5[i] += cv5[i - 1]\n",
    "                cv2[i] += tmp\n",
    "                cv5[i] += tmp2\n",
    "            c2.append(cv2)\n",
    "            c5.append(cv5)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                # 上下左右的2,5个数\n",
    "                o2,o5 = r2[i][j] - (0 if j - 1 < 0 else r2[i][j - 1]),r5[i][j] - (0 if j - 1 < 0 else r5[i][j - 1])\n",
    "                \n",
    "                tp2,tp5 = (0 if i - 1 < 0 else c2[j][i - 1]),(0 if i - 1 < 0 else c5[j][i - 1])\n",
    "                lp2,lp5 = (0 if j - 1 < 0 else r2[i][j - 1]),(0 if j - 1 < 0 else r5[i][j - 1])\n",
    "                rp2,rp5 = r2[i][-1] - r2[i][j],r5[i][-1] - r5[i][j]\n",
    "                dp2,dp5 = c2[j][-1] - c2[j][i],c5[j][-1] - c5[j][i]\n",
    "                v = [[tp2,tp5],[lp2,lp5],[rp2,rp5],[dp2,dp5]]\n",
    "                ans = max(ans,min(r2[i][-1],r5[i][-1]),min(c2[j][-1],c5[j][-1]))\n",
    "                \n",
    "                for lst in range(4):\n",
    "                    l2,l5 = v[lst]\n",
    "                    for nxt in range(lst + 1,4):\n",
    "                        n2,n5 = v[nxt]\n",
    "                        ans = max(ans,min(l2 + n2 + o2,l5 + n5 + o5))\n",
    "                        \n",
    "        return ans\n",
    "                \n",
    "                \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def n5(n):\n",
    "    res = 0\n",
    "    while n%5 == 0:\n",
    "        n //= 5\n",
    "        res += 1\n",
    "    return res\n",
    "def n2(n):\n",
    "    res = 0\n",
    "    while n%2 == 0:\n",
    "        n //= 2\n",
    "        res += 1\n",
    "    return res\n",
    "def rotate_matrix(g):\n",
    "    # 获取矩阵的行数和列数\n",
    "    rows = len(g)\n",
    "    cols = len(g[0])\n",
    "    # 创建一个新的矩阵用于存储旋转后的结果\n",
    "    new_matrix = [[0] * rows for _ in range(cols)]\n",
    "    # 顺时针旋转90度\n",
    "    for i in range(rows):\n",
    "        for j in range(cols):\n",
    "            new_matrix[j][rows-1-i] = g[i][j]\n",
    "    return new_matrix\n",
    "def solve(g):\n",
    "    def h(g):\n",
    "        n, m = len(g), len(g[0])\n",
    "        # cnt_of_2, cnt_of_5\n",
    "        dp = [[[0, 0] for _ in range(m+1)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                cnt2, cnt5 = n2(g[i][j]), n5(g[i][j])\n",
    "                dp[i][j+1][0] = dp[i][j][0] + cnt2\n",
    "                dp[i][j+1][1] = dp[i][j][1] + cnt5\n",
    "        res = 0\n",
    "        for j in range(m):\n",
    "            cnt2, cnt5 = 0, 0\n",
    "            for i in range(n):\n",
    "                t2, t5 = n2(g[i][j]), n5(g[i][j])\n",
    "                cnt2 += t2\n",
    "                cnt5 += t5\n",
    "                res = max(res, min(dp[i][j][0]+cnt2, dp[i][j][1]+cnt5))\n",
    "        for j in range(m):\n",
    "            cnt2, cnt5 = 0, 0\n",
    "            for i in reversed(range(n)):\n",
    "                t2, t5 = n2(g[i][j]), n5(g[i][j])\n",
    "                cnt2 += t2\n",
    "                cnt5 += t5\n",
    "                res = max(res, min(dp[i][j][0]+cnt2, dp[i][j][1]+cnt5))\n",
    "        return res\n",
    "    return max(h(g), h([gi[::-1] for gi in g]))\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, g: List[List[int]]) -> int:\n",
    "        return solve(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def get5(num):\n",
    "            cnt=0\n",
    "            while num%5==0:\n",
    "                cnt+=1\n",
    "                num//=5\n",
    "            return cnt\n",
    "        @lru_cache(None)\n",
    "        def get2(num):\n",
    "            cnt=0\n",
    "            while num%2==0:\n",
    "                cnt+=1\n",
    "                num//=2\n",
    "            return cnt\n",
    "        pre_row_2=[]\n",
    "        pre_row_5=[]\n",
    "        pre_col_2=[]\n",
    "        pre_col_5=[]\n",
    "        for i in range(m):\n",
    "            pre_row_2.append([0])\n",
    "            pre_row_5.append([0])\n",
    "            for j in range(n):\n",
    "                pre_row_2[-1].append(pre_row_2[-1][-1]+get2(grid[i][j]))\n",
    "                pre_row_5[-1].append(pre_row_5[-1][-1]+get5(grid[i][j]))\n",
    "        for j in range(n):\n",
    "            pre_col_2.append([0])\n",
    "            pre_col_5.append([0])\n",
    "            for i in range(m):\n",
    "                pre_col_2[-1].append(pre_col_2[-1][-1]+get2(grid[i][j]))\n",
    "                pre_col_5[-1].append(pre_col_5[-1][-1]+get5(grid[i][j]))\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                num2=get2(grid[i][j])\n",
    "                num5=get5(grid[i][j])\n",
    "                l_num2=pre_row_2[i][j]\n",
    "                t_num2=pre_col_2[j][i]\n",
    "                r_num2=pre_row_2[i][-1]-pre_row_2[i][j+1]\n",
    "                b_num2=pre_col_2[j][-1]-pre_col_2[j][i+1]\n",
    "                l_num5=pre_row_5[i][j]\n",
    "                t_num5=pre_col_5[j][i]\n",
    "                r_num5=pre_row_5[i][-1]-pre_row_5[i][j+1]\n",
    "                b_num5=pre_col_5[j][-1]-pre_col_5[j][i+1]\n",
    "                lt=min(l_num2+t_num2+num2,l_num5+t_num5+num5)\n",
    "                lb=min(l_num2+b_num2+num2,l_num5+b_num5+num5)\n",
    "                rt=min(r_num2+t_num2+num2,r_num5+t_num5+num5)\n",
    "                rb=min(r_num2+b_num2+num2,r_num5+b_num5+num5)\n",
    "                ans=max(ans,max(lt,lb,rt,rb))\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        # 分析：\n",
    "        # 路径两端肯定延长到矩阵边界是最优解\n",
    "        # 枚举转角位置，至多一个弯，可以没有弯,所以角落的元素也可以枚举\n",
    "        # 尾随0的个数 = min(cnt2,cnt5) + cnt0\n",
    "\n",
    "        def f(x):\n",
    "            # 计算x中包含的0,2,5的个数\n",
    "            cnt0 = cnt2 = cnt5 = 0\n",
    "            t = x\n",
    "            while t:\n",
    "                if t % 10 == 0:\n",
    "                    t //= 10\n",
    "                    cnt0 += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            t = x\n",
    "            while t:\n",
    "                if t % 2 == 0:\n",
    "                    t //= 2\n",
    "                    cnt2 += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            t = x\n",
    "            while t:\n",
    "                if t % 5 == 0:\n",
    "                    t //= 5\n",
    "                    cnt5 += 1\n",
    "                else:\n",
    "                    break\n",
    "            return cnt0,cnt2,cnt5\n",
    "\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        v_cnt2 = [[0]*(m + 1) for _ in range(n)]\n",
    "        v_cnt5 = [[0]*(m + 1) for _ in range(n)]\n",
    "        v_cnt0 = [[0]*(m + 1) for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            for i in range(1,m + 1):\n",
    "                a,b,c = f(grid[i - 1][j])\n",
    "                v_cnt0[j][i] = v_cnt0[j][i - 1] + a\n",
    "                v_cnt2[j][i] = v_cnt2[j][i - 1] + b\n",
    "                v_cnt5[j][i] = v_cnt5[j][i - 1] + c\n",
    "\n",
    "        h_cnt0 = [[0]*(n + 1) for _ in range(m)]\n",
    "        h_cnt5 = [[0]*(n + 1) for _ in range(m)]\n",
    "        h_cnt2 = [[0]*(n + 1) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(1,n + 1):\n",
    "                a,b,c = f(grid[i][j - 1])\n",
    "                h_cnt0[i][j] = h_cnt0[i][j - 1] + a\n",
    "                h_cnt2[i][j] = h_cnt2[i][j - 1] + b\n",
    "                h_cnt5[i][j] = h_cnt5[i][j - 1] + c\n",
    "\n",
    "        ans = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i == 3 and j == 4:\n",
    "                    print('here')\n",
    "                # 左+上\n",
    "                cnt0 = 0\n",
    "                cnt2 = h_cnt2[i][j + 1] + v_cnt2[j][i]\n",
    "                cnt5 = h_cnt5[i][j + 1] + v_cnt5[j][i]\n",
    "                ans = max(ans,cnt0 + min(cnt2,cnt5))\n",
    "\n",
    "                # 右+上\n",
    "                cnt0 = 0\n",
    "                cnt2 = h_cnt2[i][-1] - h_cnt2[i][j] + v_cnt2[j][i]\n",
    "                cnt5 = h_cnt5[i][-1] - h_cnt5[i][j] + v_cnt5[j][i]\n",
    "                ans = max(ans,cnt0 + min(cnt2,cnt5))\n",
    "\n",
    "                # 左 + 下\n",
    "                cnt0 = 0\n",
    "                cnt2 = h_cnt2[i][j + 1] + v_cnt2[j][-1] - v_cnt2[j][i + 1]\n",
    "                cnt5 = h_cnt5[i][j + 1] + v_cnt5[j][-1] - v_cnt5[j][i + 1]\n",
    "                ans = max(ans,cnt0 + min(cnt2,cnt5))\n",
    "\n",
    "                # 右 + 下\n",
    "                cnt0 = 0\n",
    "                cnt2 = h_cnt2[i][-1] - h_cnt2[i][j] + v_cnt2[j][-1] - v_cnt2[j][i + 1]\n",
    "                cnt5 = h_cnt5[i][-1] - h_cnt5[i][j] + v_cnt5[j][-1] - v_cnt5[j][i + 1]\n",
    "                ans = max(ans,cnt0 + min(cnt2,cnt5))\n",
    "\n",
    "                if ans == 6:\n",
    "                    print(i,j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        h2 = [[0] * (n + 1) for r in range(m)]\n",
    "        h5 = [[0] * (n + 1) for r in range(m)]\n",
    "        v2 = [[0] * n for r in range(m+1)]\n",
    "        v5 = [[0] * n for r in range(m+1)]\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                x = grid[r][c]\n",
    "                d2, d5 = 0, 0\n",
    "                while x % 2 == 0:\n",
    "                    d2 += 1\n",
    "                    x //= 2\n",
    "                while x % 5 == 0:\n",
    "                    d5 += 1\n",
    "                    x //= 5\n",
    "                h2[r][c+1] = h2[r][c] + d2\n",
    "                h5[r][c+1] = h5[r][c] + d5\n",
    "                v2[r+1][c] = v2[r][c] + d2\n",
    "                v5[r+1][c] = v5[r][c] + d5\n",
    "        res = 0\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                L2, L5 = h2[r][c], h5[r][c]\n",
    "                R2, R5 = h2[r][n] - h2[r][c+1], h5[r][n] - h5[r][c+1]\n",
    "                U2, U5 = v2[r+1][c], v5[r+1][c]\n",
    "                D2, D5 = v2[m][c] - v2[r][c], v5[m][c] - v5[r][c]\n",
    "                res = max(res, min(L2 + U2, L5 + U5))\n",
    "                res = max(res, min(L2 + D2, L5 + D5))\n",
    "                res = max(res, min(R2 + U2, R5 + U5))\n",
    "                res = max(res, min(R2 + D2, R5 + D5))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        #1.预处理出num中因子2和5的个数\n",
    "        factor2 = [0] * 1001    # factor2[num]: num中因子2的个数\n",
    "        factor5 = [0] * 1001    # factor5[num]: num中因子5的个数\n",
    "        for num in range(1, 1001):\n",
    "            if num % 2 == 0:factor2[num] = factor2[num//2] + 1\n",
    "            if num % 5 == 0:factor5[num] = factor5[num//5] + 1\n",
    "\n",
    "        #2.统计行、列方向因子2和5的前缀和\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # row2[i][j]: 第i行，[0, j]列中因子2的数目的前缀和【行前缀和】\n",
    "        # col2[i][j]: 第j列，[0, i]行中因子2的数目的前缀和【列前缀和】\n",
    "        row2 = [[0] * (n+1) for _ in range(m+1)]\n",
    "        row5 = [[0] * (n+1) for _ in range(m+1)]\n",
    "        col2 = [[0] * (n+1) for _ in range(m+1)]\n",
    "        col5 = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                num = grid[i-1][j-1]    # 当前转角点\n",
    "                row2[i][j] = row2[i][j-1] + factor2[num]\n",
    "                row5[i][j] = row5[i][j-1] + factor5[num]\n",
    "                col2[i][j] = col2[i-1][j] + factor2[num]\n",
    "                col5[i][j] = col5[i-1][j] + factor5[num]\n",
    "        \n",
    "        #3.计算行、列组成的转角中结尾0的数目\n",
    "        ans = 0\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                num = grid[i-1][j-1]    # 当前转角点\n",
    "                # 【行】转角点左侧和右侧数字中因子2和5的数目之和\n",
    "                left = (row2[i][j-1], row5[i][j-1])     #  (2的数目之和，5的数目之和)\n",
    "                right = (row2[i][n]-row2[i][j], row5[i][n]-row5[i][j])\n",
    "                # 【列】转角点上侧和下侧数字中因子2和5的数目之和\n",
    "                up = (col2[i-1][j], col5[i-1][j])       #  (2的数目之和，5的数目之和)\n",
    "                down = (col2[m][j]-col2[i][j], col5[m][j]-col5[i][j])\n",
    "                # 四种转角组合 (left, up) (left, down) (right, up) (right, down)\n",
    "                ans = max(ans, min(left[0]+up[0]+factor2[num], left[1]+up[1]+factor5[num]))\n",
    "                ans = max(ans, min(left[0]+down[0]+factor2[num], left[1]+down[1]+factor5[num]))\n",
    "                ans = max(ans, min(right[0]+up[0]+factor2[num], right[1]+up[1]+factor5[num]))\n",
    "                ans = max(ans, min(right[0]+down[0]+factor2[num], right[1]+down[1]+factor5[num]))      \n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        two, five = [[0] * (m + 1) for i in range(n + 1)], \\\n",
    "                    [[0] * (m + 1) for i in range(n + 1)]\n",
    "        twos, fives = [[0] * (m + 1) for i in range(n + 1)], \\\n",
    "                      [[0] * (m + 1) for i in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                cnt2, cnt5 = 0, 0\n",
    "                while grid[i][j] % 2 == 0:\n",
    "                    cnt2 += 1\n",
    "                    grid[i][j] /= 2\n",
    "                while grid[i][j] % 5 == 0:\n",
    "                    cnt5 += 1\n",
    "                    grid[i][j] /= 5\n",
    "                two[i + 1][j + 1] = two[i + 1][j] + cnt2\n",
    "                five[i + 1][j + 1] = five[i + 1][j] + cnt5\n",
    "                twos[i + 1][j + 1] = twos[i][j + 1] + cnt2\n",
    "                fives[i + 1][j + 1] = fives[i][j + 1] + cnt5\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                upL = min(twos[i + 1][j + 1] + two[i + 1][j],\n",
    "                          fives[i + 1][j + 1] + five[i + 1][j])\n",
    "                upR = min(twos[i][j + 1] + two[i + 1][m] - two[i + 1][j],\n",
    "                          fives[i][j + 1] + five[i + 1][m] - five[i + 1][j])\n",
    "                downL = min(twos[n][j + 1] - twos[i + 1][j + 1] + two[i + 1][j + 1],\n",
    "                            fives[n][j + 1] - fives[i + 1][j + 1] + five[i + 1][j + 1])\n",
    "                downR = min(twos[n][j + 1] - twos[i + 1][j + 1] + two[i + 1][m] - two[i + 1][j],\n",
    "                            fives[n][j + 1] - fives[i + 1][j + 1] + five[i + 1][m] - five[i + 1][j])\n",
    "                cnt0 = max(min(two[i + 1][m], five[i + 1][m])\n",
    "                           , min(twos[n][j + 1], fives[n][j + 1]),\n",
    "                           upL, upR, downL, downR)\n",
    "                ret = max(ret, cnt0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def get_cnt(num, factor):\n",
    "            if num % factor:\n",
    "                return 0\n",
    "            return 1 + get_cnt(num // factor, factor)\n",
    "        f2 = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        f5 = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                f2[i][j][0] = (f2[i - 1][j][0] if i > 0 else 0) + get_cnt(grid[i][j], 2)\n",
    "                f2[i][j][1] = (f2[i][j - 1][1] if j > 0 else 0) + get_cnt(grid[i][j], 2)\n",
    "                f5[i][j][0] = (f5[i - 1][j][0] if i > 0 else 0) + get_cnt(grid[i][j], 5)\n",
    "                f5[i][j][1] = (f5[i][j - 1][1] if j > 0 else 0) + get_cnt(grid[i][j], 5)\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = max(res, min(f2[i][j][0] + (f2[i][j - 1][1] if j > 0 else 0), f5[i][j][0] + (f5[i][j - 1][1] if j > 0 else 0)))\n",
    "                res = max(res, min(f2[i][j][0] + f2[i][-1][1] - f2[i][j][1], f5[i][j][0] + f5[i][-1][1] - f5[i][j][1]))\n",
    "                res = max(res, min(f2[-1][j][0] - (f2[i - 1][j][0] if i > 0 else 0) + (f2[i][j - 1][1] if j > 0 else 0), f5[-1][j][0] - (f5[i - 1][j][0] if i > 0 else 0) + (f5[i][j - 1][1] if j > 0 else 0)))\n",
    "                res = max(res, min(f2[-1][j][0] - (f2[i - 1][j][0] if i > 0 else 0) + f2[i][-1][1] - f2[i][j][1], f5[-1][j][0] - (f5[i - 1][j][0] if i > 0 else 0) + f5[i][-1][1] - f5[i][j][1]))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def calc25(num):\n",
    "            cnt_2, cnt_5 = 0, 0\n",
    "            while(num % 2 == 0):\n",
    "                cnt_2 += 1\n",
    "                num = num//2\n",
    "            while(num % 5 == 0):\n",
    "                cnt_5 += 1\n",
    "                num = num//5\n",
    "            return cnt_2, cnt_5\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = calc25(grid[i][j])\n",
    "        prerow = [[[0,0]] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prerow[i].append([prerow[i][-1][0]+grid[i][j][0], prerow[i][-1][1]+grid[i][j][1]]) \n",
    "        precol = [[[0,0]] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                precol[j].append([precol[j][-1][0]+grid[i][j][0], precol[j][-1][1]+grid[i][j][1]])\n",
    "        result = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                row1_2, row1_5 = prerow[i][j][0], prerow[i][j][1]\n",
    "                row2_2, row2_5 = prerow[i][-1][0] - row1_2 - grid[i][j][0], prerow[i][-1][1] - row1_5 - grid[i][j][1]\n",
    "\n",
    "                col1_2, col1_5 = precol[j][i][0], precol[j][i][1]\n",
    "                col2_2, col2_5 = precol[j][-1][0] - col1_2 - grid[i][j][0], precol[j][-1][1] - col1_5 - grid[i][j][1]\n",
    "\n",
    "                result = max(result\n",
    "                , min(row1_2+col1_2+grid[i][j][0], row1_5+col1_5+grid[i][j][1])\n",
    "                , min(row1_2+col2_2+grid[i][j][0], row1_5+col2_5+grid[i][j][1])\n",
    "                , min(row2_2+col1_2+grid[i][j][0], row2_5+col1_5+grid[i][j][1])\n",
    "                , min(row2_2+col2_2+grid[i][j][0], row2_5+col2_5+grid[i][j][1])\n",
    "                )\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "factor2 = [0 for _ in range(1001)]\n",
    "factor5 = [0 for _ in range(1001)]\n",
    "for i in range(1, 1001):\n",
    "    if i % 2 == 0:\n",
    "        factor2[i] = factor2[i//2] + 1\n",
    "    if i % 5 == 0:\n",
    "        factor5[i] = factor5[i//5] + 1\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # row2[i][j]: 第i行，[0, j]中因子2的数目的前缀和【行前缀和】\n",
    "        # col2[i][j]: 第j列，[0, i]行中因子2的数目的前缀和【列前缀和】\n",
    "        row2 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        row5 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        col2 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        col5 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                num = grid[i][j]    # 当前转角点\n",
    "                row2[i][j] = row2[i][j-1] + factor2[num] if j >=1 else factor2[num]\n",
    "                row5[i][j] = row5[i][j-1] + factor5[num] if j >=1 else factor5[num] \n",
    "\n",
    "                col2[i][j] = col2[i-1][j] + factor2[num] if i >=1 else factor2[num]\n",
    "                col5[i][j] = col5[i-1][j] + factor5[num] if i >=1 else factor5[num]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                num = grid[i][j]    # 当前转角点\n",
    "                \n",
    "                left = (row2[i][j-1], row5[i][j-1]) if j >= 1 else (0, 0)\n",
    "                right = (row2[i][-1]-row2[i][j], row5[i][-1]-row5[i][j])\n",
    "                \n",
    "                up = (col2[i-1][j], col5[i-1][j]) if i >= 1 else (0, 0)\n",
    "                down = (col2[-1][j]-col2[i][j], col5[-1][j]-col5[i][j])\n",
    "                \n",
    "                # 四种转角组合 (left, up) (left, down) (right, up) (right, down)\n",
    "                ans = max(ans, min(left[0]+up[0]+factor2[num], left[1]+up[1]+factor5[num]))\n",
    "                ans = max(ans, min(left[0]+down[0]+factor2[num], left[1]+down[1]+factor5[num]))\n",
    "                ans = max(ans, min(right[0]+up[0]+factor2[num], right[1]+up[1]+factor5[num]))\n",
    "                ans = max(ans, min(right[0]+down[0]+factor2[num], right[1]+down[1]+factor5[num]))\n",
    "                \n",
    "        return ans        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        def calc25(num):\n",
    "            cnt_2, cnt_5 = 0, 0\n",
    "            while(num % 2 == 0):\n",
    "                cnt_2 += 1\n",
    "                num = num//2\n",
    "            while(num % 5 == 0):\n",
    "                cnt_5 += 1\n",
    "                num = num//5\n",
    "            return cnt_2, cnt_5\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = calc25(grid[i][j])\n",
    "        prerow = [[[0,0]] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prerow[i].append([prerow[i][-1][0]+grid[i][j][0], prerow[i][-1][1]+grid[i][j][1]]) \n",
    "        precol = [[[0,0]] for _ in range(n)]\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                precol[j].append([precol[j][-1][0]+grid[i][j][0], precol[j][-1][1]+grid[i][j][1]])\n",
    "        result = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                row1_2, row1_5 = prerow[i][j][0], prerow[i][j][1]\n",
    "                row2_2, row2_5 = prerow[i][-1][0] - row1_2 - grid[i][j][0], prerow[i][-1][1] - row1_5 - grid[i][j][1]\n",
    "\n",
    "                col1_2, col1_5 = precol[j][i][0], precol[j][i][1]\n",
    "                col2_2, col2_5 = precol[j][-1][0] - col1_2 - grid[i][j][0], precol[j][-1][1] - col1_5 - grid[i][j][1]\n",
    "\n",
    "                result = max(result\n",
    "                , min(row1_2+col1_2+grid[i][j][0], row1_5+col1_5+grid[i][j][1])\n",
    "                , min(row1_2+col2_2+grid[i][j][0], row1_5+col2_5+grid[i][j][1])\n",
    "                , min(row2_2+col1_2+grid[i][j][0], row2_5+col1_5+grid[i][j][1])\n",
    "                , min(row2_2+col2_2+grid[i][j][0], row2_5+col2_5+grid[i][j][1])\n",
    "                )\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def get25(self, n):\n",
    "        if n == 0:\n",
    "            return 0, 0\n",
    "        n2 = 0\n",
    "        while n % 2 == 0:\n",
    "            n2 += 1\n",
    "            n //= 2\n",
    "        n5 = 0\n",
    "        while n % 5 == 0:\n",
    "            n5 += 1\n",
    "            n //= 5\n",
    "        return n2, n5\n",
    "\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        S, L, R, U, D = 0, 1, 2, 3, 4\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[(0, 0)] * 5 for _ in range(n)] for _ in range(m)]\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                dp[r][c][0] = self.get25(grid[r][c])\n",
    "\n",
    "        for r in range(m):\n",
    "            dp[r][0][L] = dp[r][0][S]\n",
    "            for c in range(1, n):\n",
    "                dp[r][c][L] = (\n",
    "                    dp[r][c - 1][L][0] + dp[r][c][S][0],\n",
    "                    dp[r][c - 1][L][1] + dp[r][c][S][1],\n",
    "                )\n",
    "\n",
    "        for r in range(m):\n",
    "            dp[r][-1][R] = dp[r][-1][0]\n",
    "            for c in range(n - 2, -1, -1):\n",
    "                dp[r][c][R] = (\n",
    "                    dp[r][c + 1][R][0] + dp[r][c][S][0],\n",
    "                    dp[r][c + 1][R][1] + dp[r][c][S][1],\n",
    "                )\n",
    "\n",
    "        for c in range(n):\n",
    "            dp[0][c][U] = dp[0][c][S]\n",
    "            for r in range(1, m):\n",
    "                dp[r][c][U] = (\n",
    "                    dp[r - 1][c][U][0] + dp[r][c][S][0],\n",
    "                    dp[r - 1][c][U][1] + dp[r][c][S][1],\n",
    "                )\n",
    "\n",
    "        for c in range(n):\n",
    "            dp[-1][c][D] = dp[-1][c][S]\n",
    "            for r in range(m - 2, -1, -1):\n",
    "                dp[r][c][D] = (\n",
    "                    dp[r + 1][c][D][0] + dp[r][c][S][0],\n",
    "                    dp[r + 1][c][D][1] + dp[r][c][S][1],\n",
    "                )\n",
    "\n",
    "        ans = 0\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                x = 0\n",
    "                for a in range(1, 5):\n",
    "                    for b in range(a + 1, 5):\n",
    "                        x = max(\n",
    "                            x,\n",
    "                            min(\n",
    "                                dp[r][c][a][0] + dp[r][c][b][0] - dp[r][c][0][0],\n",
    "                                dp[r][c][a][1] + dp[r][c][b][1] - dp[r][c][0][1],\n",
    "                            ),\n",
    "                        )\n",
    "                ans = max(ans, x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@lru_cache(None)\n",
    "def check(num, t):\n",
    "    res = 0\n",
    "    while num % t == 0:\n",
    "        num //= t\n",
    "        res += 1\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        two = [[check(grid[i][j], 2) for j in range(n)] for i in range(m)]\n",
    "        five = [[check(grid[i][j], 5) for j in range(n)] for i in range(m)]\n",
    "\n",
    "        psr2 = [list(accumulate(two[i], initial=0)) for i in range(m)]\n",
    "        psr5 = [list(accumulate(five[i], initial=0)) for i in range(m)]\n",
    "\n",
    "        psc2 = [list(accumulate([two[i][j] for i in range(m)], initial=0)) for j in range(n)]\n",
    "        psc5 = [list(accumulate([five[i][j] for i in range(m)], initial=0)) for j in range(n)]\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a = psr2[i][j + 1] + psc2[j][i + 1] - two[i][j]\n",
    "                b = psr5[i][j + 1] + psc5[j][i + 1] - five[i][j]\n",
    "                ans = max(ans, min(a, b))\n",
    "                \n",
    "                a = psr2[i][j + 1] + psc2[j][-1] - psc2[j][i] - two[i][j]\n",
    "                b = psr5[i][j + 1] + psc5[j][-1] - psc5[j][i] - five[i][j]\n",
    "                ans = max(ans, min(a, b))\n",
    "\n",
    "                a = psr2[i][-1] - psr2[i][j] + psc2[j][i + 1] - two[i][j]\n",
    "                b = psr5[i][-1] - psr5[i][j] + psc5[j][i + 1] - five[i][j]\n",
    "                ans = max(ans, min(a, b))\n",
    "\n",
    "                a = psr2[i][-1] - psr2[i][j] + psc2[j][-1] - psc2[j][i] - two[i][j]\n",
    "                b = psr5[i][-1] - psr5[i][j] + psc5[j][-1] - psc5[j][i] - five[i][j]\n",
    "                ans = max(ans, min(a, b))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        g = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j,v in enumerate(grid[i]):\n",
    "                while v % 2 == 0:\n",
    "                    f[i][j] += 1\n",
    "                    v //= 2\n",
    "                while v % 5 == 0:\n",
    "                    g[i][j] += 1\n",
    "                    v //= 5\n",
    "        \n",
    "        f1 = [list(itertools.accumulate(x, initial=0)) for x in f]\n",
    "        g1 = [list(itertools.accumulate(x, initial=0)) for x in g]\n",
    "        f2 = [list(itertools.accumulate(x, initial=0)) for x in zip(*f)]\n",
    "        g2 = [list(itertools.accumulate(x, initial=0)) for x in zip(*g)]\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c = [[0]*2 for _ in range(4)]\n",
    "                c[0][0] = f1[i][j+1]\n",
    "                c[0][1] = g1[i][j+1]\n",
    "                c[1][0] = f1[i][-1] - f1[i][j]\n",
    "                c[1][1] = g1[i][-1] - g1[i][j]\n",
    "                c[2][0] = f2[j][i+1]\n",
    "                c[2][1] = g2[j][i+1]\n",
    "                c[3][0] = f2[j][-1] - f2[j][i]\n",
    "                c[3][1] = g2[j][-1] - g2[j][i]\n",
    "                for a,b in itertools.product([c[0], c[1]], [c[2], c[3]]):\n",
    "                    x = [a[0]+b[0]-f[i][j], a[1]+b[1]-g[i][j]]\n",
    "                    ans = max(ans, min(x))\n",
    "\n",
    "        for i in range(m):\n",
    "            ans = max(ans, min(f1[i][-1], g1[i][-1]))\n",
    "        for j in range(n):\n",
    "            ans = max(ans, min(f2[j][-1], g2[j][-1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        \n",
    "        f = [[[0, 0, 0, 0] for i in range(n + 1)] for j in range(m + 1)]\n",
    "        r2 = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        r5 = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        c2 = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        c5 = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                k = grid[i][j]\n",
    "                two = five = 0\n",
    "                while k & 1 == 0:\n",
    "                    k >>= 1\n",
    "                    two += 1\n",
    "                while k % 5 == 0:\n",
    "                    k //= 5\n",
    "                    five += 1\n",
    "                    \n",
    "                r2[i + 1][j + 1] = r2[i + 1][j] + two\n",
    "                r5[i + 1][j + 1] = r5[i + 1][j] + five\n",
    "                \n",
    "                c2[i + 1][j + 1] = c2[i][j + 1] + two\n",
    "                c5[i + 1][j + 1] = c5[i][j + 1] + five\n",
    "        # print(f)\n",
    "                \n",
    "        ret = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                a1 = min(r2[i + 1][j + 1] + c2[i][j + 1], r5[i + 1][j + 1] + c5[i][j + 1])\n",
    "                a2 = min(r2[i + 1][n] - r2[i + 1][j] + c2[i][j + 1], r5[i + 1][n] - r5[i + 1][j] + c5[i][j + 1])\n",
    "                a3 = min(r2[i + 1][j + 1] + c2[m][j + 1] - c2[i + 1][j + 1], r5[i + 1][j + 1] + c5[m][j + 1] - c5[i + 1][j + 1])\n",
    "                a4 = min(r2[i + 1][n] - r2[i + 1][j] + c2[m][j + 1] - c2[i + 1][j + 1], r5[i + 1][n] - r5[i + 1][j] + c5[m][j + 1] - c5[i + 1][j + 1])\n",
    "                ret = max(ret, a1, a2, a3, a4)\n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        left_25_num = [[0] * n for i in range(m)]\n",
    "        right_25_num = [[0] * n for i in range(m)]\n",
    "        up_25_num = [[0] * n for i in range(m)]\n",
    "        down_25_num = [[0] * n for i in range(m)]\n",
    "        this_25_num = [[0] * n for i in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                num = grid[i][j]\n",
    "                num_2 = 0\n",
    "                while num % 2 == 0:\n",
    "                    num_2 += 1\n",
    "                    num //= 2\n",
    "                \n",
    "                num_5 = 0\n",
    "                while num % 5 == 0:\n",
    "                    num_5 += 1\n",
    "                    num //= 5\n",
    "                \n",
    "                this_25_num[i][j] = (num_2, num_5)\n",
    "        \n",
    "                if i == 0:\n",
    "                    up_25_num[i][j] = this_25_num[i][j]\n",
    "                else:\n",
    "                    last_2_num = up_25_num[i - 1][j][0]\n",
    "                    last_5_num = up_25_num[i - 1][j][1]\n",
    "                    up_25_num[i][j] = (last_2_num + num_2, last_5_num + num_5)\n",
    "                \n",
    "                if j == 0:\n",
    "                    left_25_num[i][j] = this_25_num[i][j]\n",
    "                else:\n",
    "                    last_2_num = left_25_num[i][j - 1][0]\n",
    "                    last_5_num = left_25_num[i][j - 1][1]\n",
    "                    left_25_num[i][j] = (last_2_num + num_2, last_5_num + num_5)\n",
    "        \n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                num_2, num_5 = this_25_num[i][j]\n",
    "\n",
    "                if i == m - 1:\n",
    "                    down_25_num[i][j] = (num_2, num_5)\n",
    "                else:\n",
    "                    last_2_num = down_25_num[i + 1][j][0]\n",
    "                    last_5_num = down_25_num[i + 1][j][1]\n",
    "                    down_25_num[i][j] = (last_2_num + num_2, last_5_num + num_5)\n",
    "                \n",
    "                if j == n - 1:\n",
    "                    right_25_num[i][j] = (num_2, num_5)\n",
    "                else:\n",
    "                    last_2_num = right_25_num[i][j + 1][0]\n",
    "                    last_5_num = right_25_num[i][j + 1][1]\n",
    "                    right_25_num[i][j] = (last_2_num + num_2, last_5_num + num_5)\n",
    "\n",
    "        max_0_num = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                hori_opt = (left_25_num[i][j], right_25_num[i][j])\n",
    "                vert_opt = (up_25_num[i][j], down_25_num[i][j])\n",
    "\n",
    "                this_2_num, this_5_num = this_25_num[i][j]\n",
    "\n",
    "                for hori_select in hori_opt:\n",
    "                    for vert_select in vert_opt:\n",
    "                        num2 = hori_select[0] + vert_select[0] - this_2_num\n",
    "                        num5 = hori_select[1] + vert_select[1] - this_5_num\n",
    "                        max_0_num = max(max_0_num, min(num2, num5))\n",
    "        \n",
    "        return max_0_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "#         def div(x, f):\n",
    "#             ans = 0\n",
    "#             while(x%f==0 and x>0):\n",
    "#                 ans += 1\n",
    "#                 x = x//f\n",
    "#             return ans\n",
    "        \n",
    "#         n, m = len(grid), len(grid[0])\n",
    "#         grid5 = [[div(grid[i][j], 5) for j in range(m)] for i in range(n)]\n",
    "#         grid2 = [[div(grid[i][j], 2) for j in range(m)] for i in range(n)]\n",
    "#         pregrid5row, pregrid5col, pregrid2row, pregrid2col = [], [], [], []\n",
    "#         for i in range(n):\n",
    "#             tmp2, tmp5 = [0], [0]\n",
    "#             for j in range(m):\n",
    "#                 tmp2.append(grid2[i][j] + tmp2[-1])\n",
    "#                 tmp5.append(grid5[i][j] + tmp5[-1])\n",
    "#             pregrid2row.append(tmp2)\n",
    "#             pregrid5row.append(tmp5)\n",
    "#         for j in range(m):\n",
    "#             tmp2, tmp5 = [0], [0]\n",
    "#             for i in range(n):\n",
    "#                 tmp2.append(grid2[i][j] + tmp2[-1])\n",
    "#                 tmp5.append(grid5[i][j] + tmp5[-1])\n",
    "#             pregrid2col.append(tmp2)\n",
    "#             pregrid5col.append(tmp5)\n",
    "        \n",
    "#         def cal(x, y):\n",
    "#             tmp1, tmp2, tmp3, tmp4 = 0, 0, 0, 0\n",
    "#             tmp1 = min(pregrid5row[x][y+1] + pregrid5col[y][x+1] - div(grid[x][y], 5), pregrid2row[x][y+1] + pregrid2col[y][x+1]-div(grid[x][y], 2))\n",
    "#             tmp2 = min(pregrid5row[x][y+1] + pregrid5col[y][-1] - pregrid5col[y][x+1]- div(grid[x][y], 5), pregrid2row[x][y+1] + pregrid2col[y][-1] - pregrid2col[y][x+1]-div(grid[x][y], 2))\n",
    "#             tmp3 = min(pregrid5row[x][-1] - pregrid5row[x][y+1] + pregrid5col[y][x+1]- div(grid[x][y], 5), pregrid2row[x][-1] - pregrid2row[x][y+1] + pregrid2col[y][x+1]-div(grid[x][y], 2))\n",
    "\n",
    "#             tmp4 = min(pregrid5row[x][-1] - pregrid5row[x][y+1] + pregrid5col[y][-1] - pregrid5col[y][x+1]- div(grid[x][y], 5), pregrid2row[x][-1] - pregrid2row[x][y+1] + pregrid2col[y][-1] - pregrid2col[y][x+1]-div(grid[x][y], 2))\n",
    "#             return max(tmp1, tmp2, tmp3, tmp4)\n",
    "\n",
    "#         ans = 0\n",
    "#         for i in range(n):\n",
    "#             for j in range(m):\n",
    "#                 ans = max(ans, cal(i, j))\n",
    "#         return ans\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 计算一个整数质因数分解中 2 的数量\n",
    "        def cnt2(num: int) -> int:\n",
    "            res = 0\n",
    "            while num % 2 == 0:\n",
    "                res += 1\n",
    "                num //= 2\n",
    "            return res\n",
    "        \n",
    "        # 计算一个整数质因数分解中 5 的数量\n",
    "        def cnt5(num: int) -> int:\n",
    "            res = 0\n",
    "            while num % 5 == 0:\n",
    "                res += 1\n",
    "                num //= 5\n",
    "            return res\n",
    "        \n",
    "        # 每个方向延伸部分乘积中因子 2/5 的数量\n",
    "        l2 = [[0] * n for _ in range(m)]\n",
    "        l5 = [[0] * n for _ in range(m)]\n",
    "        r2 = [[0] * n for _ in range(m)]\n",
    "        r5 = [[0] * n for _ in range(m)]\n",
    "        u2 = [[0] * n for _ in range(m)]\n",
    "        u5 = [[0] * n for _ in range(m)]\n",
    "        d2 = [[0] * n for _ in range(m)]\n",
    "        d5 = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i:\n",
    "                    u2[i][j] = u2[i-1][j] + cnt2(grid[i-1][j])\n",
    "                    u5[i][j] = u5[i-1][j] + cnt5(grid[i-1][j])\n",
    "                if j:\n",
    "                    l2[i][j] = l2[i][j-1] + cnt2(grid[i][j-1])\n",
    "                    l5[i][j] = l5[i][j-1] + cnt5(grid[i][j-1])\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, - 1, -1):\n",
    "                if i != m - 1:\n",
    "                    d2[i][j] = d2[i+1][j] + cnt2(grid[i+1][j])\n",
    "                    d5[i][j] = d5[i+1][j] + cnt5(grid[i+1][j])\n",
    "                if j != n - 1:\n",
    "                    r2[i][j] = r2[i][j+1] + cnt2(grid[i][j+1])\n",
    "                    r5[i][j] = r5[i][j+1] + cnt5(grid[i][j+1])\n",
    "        res = 0   # 所有转角路径中乘积尾随零的最大值\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 枚举转角点\n",
    "                c2 = cnt2(grid[i][j])\n",
    "                c5 = cnt5(grid[i][j])\n",
    "                res = max(res, min(u2[i][j] + l2[i][j] + c2, u5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(u2[i][j] + r2[i][j] + c2, u5[i][j] + r5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + l2[i][j] + c2, d5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + r2[i][j] + c2, d5[i][j] + r5[i][j] + c5))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 计算一个整数质因数分解中 2 的数量\n",
    "        def cnt2(num: int) -> int:\n",
    "            res = 0\n",
    "            while num % 2 == 0:\n",
    "                res += 1\n",
    "                num //= 2\n",
    "            return res\n",
    "        \n",
    "        # 计算一个整数质因数分解中 5 的数量\n",
    "        def cnt5(num: int) -> int:\n",
    "            res = 0\n",
    "            while num % 5 == 0:\n",
    "                res += 1\n",
    "                num //= 5\n",
    "            return res\n",
    "        \n",
    "        # 每个方向延伸部分乘积中因子 2/5 的数量\n",
    "        l2 = [[0] * n for _ in range(m)]\n",
    "        l5 = [[0] * n for _ in range(m)]\n",
    "        r2 = [[0] * n for _ in range(m)]\n",
    "        r5 = [[0] * n for _ in range(m)]\n",
    "        u2 = [[0] * n for _ in range(m)]\n",
    "        u5 = [[0] * n for _ in range(m)]\n",
    "        d2 = [[0] * n for _ in range(m)]\n",
    "        d5 = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i:\n",
    "                    u2[i][j] = u2[i-1][j] + cnt2(grid[i-1][j])\n",
    "                    u5[i][j] = u5[i-1][j] + cnt5(grid[i-1][j])\n",
    "                if j:\n",
    "                    l2[i][j] = l2[i][j-1] + cnt2(grid[i][j-1])\n",
    "                    l5[i][j] = l5[i][j-1] + cnt5(grid[i][j-1])\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, - 1, -1):\n",
    "                if i != m - 1:\n",
    "                    d2[i][j] = d2[i+1][j] + cnt2(grid[i+1][j])\n",
    "                    d5[i][j] = d5[i+1][j] + cnt5(grid[i+1][j])\n",
    "                if j != n - 1:\n",
    "                    r2[i][j] = r2[i][j+1] + cnt2(grid[i][j+1])\n",
    "                    r5[i][j] = r5[i][j+1] + cnt5(grid[i][j+1])\n",
    "        res = 0   # 所有转角路径中乘积尾随零的最大值\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 枚举转角点\n",
    "                c2 = cnt2(grid[i][j])\n",
    "                c5 = cnt5(grid[i][j])\n",
    "                res = max(res, min(u2[i][j] + l2[i][j] + c2, u5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(u2[i][j] + r2[i][j] + c2, u5[i][j] + r5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + l2[i][j] + c2, d5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + r2[i][j] + c2, d5[i][j] + r5[i][j] + c5))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 计算一个整数质因数分解中 2 的数量\n",
    "        def cnt2(num: int) -> int:\n",
    "            res = 0\n",
    "            while num % 2 == 0:\n",
    "                res += 1\n",
    "                num //= 2\n",
    "            return res\n",
    "        \n",
    "        # 计算一个整数质因数分解中 5 的数量\n",
    "        def cnt5(num: int) -> int:\n",
    "            res = 0\n",
    "            while num % 5 == 0:\n",
    "                res += 1\n",
    "                num //= 5\n",
    "            return res\n",
    "        \n",
    "        # 每个方向延伸部分乘积中因子 2/5 的数量\n",
    "        l2 = [[0] * n for _ in range(m)]\n",
    "        l5 = [[0] * n for _ in range(m)]\n",
    "        r2 = [[0] * n for _ in range(m)]\n",
    "        r5 = [[0] * n for _ in range(m)]\n",
    "        u2 = [[0] * n for _ in range(m)]\n",
    "        u5 = [[0] * n for _ in range(m)]\n",
    "        d2 = [[0] * n for _ in range(m)]\n",
    "        d5 = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i:\n",
    "                    u2[i][j] = u2[i-1][j] + cnt2(grid[i-1][j])\n",
    "                    u5[i][j] = u5[i-1][j] + cnt5(grid[i-1][j])\n",
    "                if j:\n",
    "                    l2[i][j] = l2[i][j-1] + cnt2(grid[i][j-1])\n",
    "                    l5[i][j] = l5[i][j-1] + cnt5(grid[i][j-1])\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, - 1, -1):\n",
    "                if i != m - 1:\n",
    "                    d2[i][j] = d2[i+1][j] + cnt2(grid[i+1][j])\n",
    "                    d5[i][j] = d5[i+1][j] + cnt5(grid[i+1][j])\n",
    "                if j != n - 1:\n",
    "                    r2[i][j] = r2[i][j+1] + cnt2(grid[i][j+1])\n",
    "                    r5[i][j] = r5[i][j+1] + cnt5(grid[i][j+1])\n",
    "        res = 0   # 所有转角路径中乘积尾随零的最大值\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 枚举转角点\n",
    "                c2 = cnt2(grid[i][j])\n",
    "                c5 = cnt5(grid[i][j])\n",
    "                res = max(res, min(u2[i][j] + l2[i][j] + c2, u5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(u2[i][j] + r2[i][j] + c2, u5[i][j] + r5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + l2[i][j] + c2, d5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + r2[i][j] + c2, d5[i][j] + r5[i][j] + c5))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 计算一个整数质因数分解中 2 的数量\n",
    "        def cnt2(num: int) -> int:\n",
    "            res = 0\n",
    "            while num % 2 == 0:\n",
    "                res += 1\n",
    "                num //= 2\n",
    "            return res\n",
    "        \n",
    "        # 计算一个整数质因数分解中 5 的数量\n",
    "        def cnt5(num: int) -> int:\n",
    "            res = 0\n",
    "            while num % 5 == 0:\n",
    "                res += 1\n",
    "                num //= 5\n",
    "            return res\n",
    "        \n",
    "        # 每个方向延伸部分乘积中因子 2/5 的数量\n",
    "        l2 = [[0] * n for _ in range(m)]\n",
    "        l5 = [[0] * n for _ in range(m)]\n",
    "        r2 = [[0] * n for _ in range(m)]\n",
    "        r5 = [[0] * n for _ in range(m)]\n",
    "        u2 = [[0] * n for _ in range(m)]\n",
    "        u5 = [[0] * n for _ in range(m)]\n",
    "        d2 = [[0] * n for _ in range(m)]\n",
    "        d5 = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i:\n",
    "                    u2[i][j] = u2[i-1][j] + cnt2(grid[i-1][j])\n",
    "                    u5[i][j] = u5[i-1][j] + cnt5(grid[i-1][j])\n",
    "                if j:\n",
    "                    l2[i][j] = l2[i][j-1] + cnt2(grid[i][j-1])\n",
    "                    l5[i][j] = l5[i][j-1] + cnt5(grid[i][j-1])\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, - 1, -1):\n",
    "                if i != m - 1:\n",
    "                    d2[i][j] = d2[i+1][j] + cnt2(grid[i+1][j])\n",
    "                    d5[i][j] = d5[i+1][j] + cnt5(grid[i+1][j])\n",
    "                if j != n - 1:\n",
    "                    r2[i][j] = r2[i][j+1] + cnt2(grid[i][j+1])\n",
    "                    r5[i][j] = r5[i][j+1] + cnt5(grid[i][j+1])\n",
    "        res = 0   # 所有转角路径中乘积尾随零的最大值\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 枚举转角点\n",
    "                c2 = cnt2(grid[i][j])\n",
    "                c5 = cnt5(grid[i][j])\n",
    "                res = max(res, min(u2[i][j] + l2[i][j] + c2, u5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(u2[i][j] + r2[i][j] + c2, u5[i][j] + r5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + l2[i][j] + c2, d5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + r2[i][j] + c2, d5[i][j] + r5[i][j] + c5))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 计算一个整数质因数分解中 base 的数量\n",
    "        def cnt(num: int, base) -> int:\n",
    "            res = 0\n",
    "            while num % base == 0:\n",
    "                res += 1\n",
    "                num //= base\n",
    "            return res\n",
    "        \n",
    "        # 每个方向延伸部分乘积中因子 2/5 的数量\n",
    "        l2 = [[0] * n for _ in range(m)]\n",
    "        l5 = [[0] * n for _ in range(m)]\n",
    "        r2 = [[0] * n for _ in range(m)]\n",
    "        r5 = [[0] * n for _ in range(m)]\n",
    "        u2 = [[0] * n for _ in range(m)]\n",
    "        u5 = [[0] * n for _ in range(m)]\n",
    "        d2 = [[0] * n for _ in range(m)]\n",
    "        d5 = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i:\n",
    "                    u2[i][j] = u2[i-1][j] + cnt(grid[i-1][j], 2)\n",
    "                    u5[i][j] = u5[i-1][j] + cnt(grid[i-1][j], 5)\n",
    "                if j:\n",
    "                    l2[i][j] = l2[i][j-1] + cnt(grid[i][j-1], 2)\n",
    "                    l5[i][j] = l5[i][j-1] + cnt(grid[i][j-1], 5)\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, - 1, -1):\n",
    "                if i != m - 1:\n",
    "                    d2[i][j] = d2[i+1][j] + cnt(grid[i+1][j], 2)\n",
    "                    d5[i][j] = d5[i+1][j] + cnt(grid[i+1][j], 5)\n",
    "                if j != n - 1:\n",
    "                    r2[i][j] = r2[i][j+1] + cnt(grid[i][j+1], 2)\n",
    "                    r5[i][j] = r5[i][j+1] + cnt(grid[i][j+1], 5)\n",
    "        res = 0   # 所有转角路径中乘积尾随零的最大值\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 枚举转角点\n",
    "                c2 = cnt(grid[i][j], 2)\n",
    "                c5 = cnt(grid[i][j], 5)\n",
    "                res = max(res, min(u2[i][j] + l2[i][j] + c2, u5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(u2[i][j] + r2[i][j] + c2, u5[i][j] + r5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + l2[i][j] + c2, d5[i][j] + l5[i][j] + c5))\n",
    "                res = max(res, min(d2[i][j] + r2[i][j] + c2, d5[i][j] + r5[i][j] + c5))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def howManyX(self, num, X):\n",
    "        ret = 0\n",
    "        while num % X == 0:\n",
    "            ret += 1\n",
    "            num =  num // X\n",
    "        return ret\n",
    "\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        TwoandFiveGrid = [[None for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "\n",
    "        leftPreSum = [[None for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        rightPreSum = [[None for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        upPreSum = [[None for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        downPreSum = [[None for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                item = grid[i][j]\n",
    "                TwoandFiveGrid[i][j] = (self.howManyX(item, 2), self.howManyX(item, 5))\n",
    "            \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if j == 0:                    \n",
    "                    leftPreSum[i][j] = (0, 0)\n",
    "                else:\n",
    "                    prev = leftPreSum[i][j-1]\n",
    "                    leftPreSum[i][j] = (prev[0] + TwoandFiveGrid[i][j-1][0], prev[1] + TwoandFiveGrid[i][j-1][1])\n",
    "        \n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in reversed(range(len(grid[0]))):\n",
    "                if j == len(grid[0]) - 1:\n",
    "                    rightPreSum[i][j] = (0, 0)\n",
    "                else:\n",
    "                    prev = rightPreSum[i][j+1]\n",
    "                    rightPreSum[i][j] = (prev[0] + TwoandFiveGrid[i][j+1][0], prev[1] + TwoandFiveGrid[i][j+1][1])\n",
    "        \n",
    "\n",
    "        for j in range(len(grid[0])):\n",
    "            for i in range(len(grid)):            \n",
    "                if i == 0:\n",
    "                    upPreSum[i][j] = (0, 0)\n",
    "                else:\n",
    "                    prev = upPreSum[i-1][j]\n",
    "                    upPreSum[i][j] = (prev[0] + TwoandFiveGrid[i-1][j][0], prev[1] + TwoandFiveGrid[i-1][j][1])\n",
    "\n",
    "        for j in range(len(grid[0])):\n",
    "            for i in reversed(range(len(grid))):            \n",
    "                if i == len(grid) - 1:\n",
    "                    downPreSum[i][j] = (0, 0)\n",
    "                else:\n",
    "                    prev = downPreSum[i+1][j]\n",
    "                    downPreSum[i][j] = (prev[0] + TwoandFiveGrid[i+1][j][0], prev[1] + TwoandFiveGrid[i+1][j][1])\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):                \n",
    "                fromleftzero = min(leftPreSum[i][j][0], leftPreSum[i][j][1])\n",
    "                fromrightzero = min(rightPreSum[i][j][0], rightPreSum[i][j][1])\n",
    "                fromtopzero = min(upPreSum[i][j][0], upPreSum[i][j][1])\n",
    "                fromdownzero = min(downPreSum[i][j][0], downPreSum[i][j][1])                \n",
    "\n",
    "                thisNodeZero = min(TwoandFiveGrid[i][j][0], TwoandFiveGrid[i][j][1])\n",
    "                #往右然后拐上\n",
    "                ret =  max(ret, min(leftPreSum[i][j][0] + upPreSum[i][j][0] + TwoandFiveGrid[i][j][0], leftPreSum[i][j][1] + upPreSum[i][j][1] + TwoandFiveGrid[i][j][1]))\n",
    "                #往右然后拐下                \n",
    "                ret =  max(ret, min(leftPreSum[i][j][0] + downPreSum[i][j][0] + TwoandFiveGrid[i][j][0], leftPreSum[i][j][1] + downPreSum[i][j][1] + TwoandFiveGrid[i][j][1]))\n",
    "                #往左然后拐上                \n",
    "                ret =  max(ret, min(rightPreSum[i][j][0] + upPreSum[i][j][0] + TwoandFiveGrid[i][j][0], rightPreSum[i][j][1] + upPreSum[i][j][1] + TwoandFiveGrid[i][j][1]))\n",
    "                #往左然后拐下\n",
    "                ret =  max(ret, min(rightPreSum[i][j][0] + downPreSum[i][j][0] + TwoandFiveGrid[i][j][0], rightPreSum[i][j][1] + downPreSum[i][j][1] + TwoandFiveGrid[i][j][1]))\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def get_counter(num):\n",
    "            c={2:0,5:0}\n",
    "            while num%2==0:\n",
    "                num=num//2\n",
    "                c[2]+=1\n",
    "            while num%5==0:\n",
    "                num=num//5\n",
    "                c[5]+=1\n",
    "            return c\n",
    "        counters=[[get_counter(grid[i][j]) for j in range(n)] for i in range(m)]\n",
    "        def add_counter(a,b):\n",
    "            return {2:a[2]+b[2],5:a[5]+b[5]}\n",
    "        def minus_counter(a,b):\n",
    "            return {2:a[2]-b[2],5:a[5]-b[5]}\n",
    "        def trans(mat):\n",
    "            nn,nm=len(mat),len(mat[0])\n",
    "            r=[[] for _ in range(nm)]\n",
    "            for i in range(nm):\n",
    "                for j in range(nn):\n",
    "                    r[i].append(mat[j][i])\n",
    "            return r\n",
    "        ver_pre=trans([list(accumulate(row, func=add_counter)) for row in trans(counters)])\n",
    "        hor_pre=[list(accumulate(row, func=add_counter)) for row in counters]\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c=counters[i][j]\n",
    "                t=ver_pre[i][j]\n",
    "                b=minus_counter(ver_pre[m-1][j], ver_pre[i][j])\n",
    "                l=hor_pre[i][j]\n",
    "                r=minus_counter(hor_pre[i][n-1], hor_pre[i][j])\n",
    "                lt=minus_counter(add_counter(l,t), c)\n",
    "                lb=add_counter(l,b)\n",
    "                rt=add_counter(r,t)\n",
    "                rb=add_counter(add_counter(r,b),c)\n",
    "                for tmp in [lt,lb,rt,rb]:\n",
    "                    c2,c5=tmp[2],tmp[5]\n",
    "                    ans=max(ans,min(c2,c5))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTrailingZeros(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        def get_counter(num):\n",
    "            c={2:0,5:0}\n",
    "            while num%2==0:\n",
    "                num=num//2\n",
    "                c[2]+=1\n",
    "            while num%5==0:\n",
    "                num=num//5\n",
    "                c[5]+=1\n",
    "            return c\n",
    "        counters=[[get_counter(grid[i][j]) for j in range(n)] for i in range(m)]\n",
    "        def add_counter(a,b):\n",
    "            return {2:a[2]+b[2],5:a[5]+b[5]}\n",
    "        def minus_counter(a,b):\n",
    "            return {2:a[2]-b[2],5:a[5]-b[5]}\n",
    "        def trans(mat):\n",
    "            nn,nm=len(mat),len(mat[0])\n",
    "            r=[[] for _ in range(nm)]\n",
    "            for i in range(nm):\n",
    "                for j in range(nn):\n",
    "                    r[i].append(mat[j][i])\n",
    "            return r\n",
    "        ver_pre=trans([list(accumulate(row, func=add_counter)) for row in trans(counters)])\n",
    "        hor_pre=[list(accumulate(row, func=add_counter)) for row in counters]\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                c=counters[i][j]\n",
    "                t=ver_pre[i][j]\n",
    "                b=minus_counter(ver_pre[m-1][j], ver_pre[i][j])\n",
    "                l=hor_pre[i][j]\n",
    "                r=minus_counter(hor_pre[i][n-1], hor_pre[i][j])\n",
    "                lt=minus_counter(add_counter(l,t), c)\n",
    "                lb=add_counter(l,b)\n",
    "                rt=add_counter(r,t)\n",
    "                rb=add_counter(add_counter(r,b),c)\n",
    "                for tmp in [lt,lb,rt,rb]:\n",
    "                    c2,c5=tmp[2],tmp[5]\n",
    "                    ans=max(ans,min(c2,c5))\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "    \n",
    "    # def __init__(self):\n",
    "    #     buff=[]\n",
    "    #     for i in range(0,1001):\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
